package com.cat.dataStructure02;

import java.util.HashMap;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-submatrices-that-sum-to-target/
 * @create 2025/10/22 19:51
 * @since JDK17
 */

public class Solution46 {
    int f(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int ans = 0, n = nums.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            map.merge(sum, 1, Integer::sum);
            sum += nums[i];
            ans += map.getOrDefault(sum - target, 0);
        }

        return ans;
    }
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int n = matrix.length, m = matrix[0].length, ans = 0;
        for (int i = 0; i < n; i++) {
            int[] col = new int[m];
            for (int j = i; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    col[k] += matrix[j][k];
                }
                ans += f(col, target);
            }
        }

        return ans;
    }
}
